package com.github.kezhenxu94.playground.leetcode;

/**
 * <pre>
 * 
 * 167. Two Sum II - Input array is sorted
 * 
 * Given an array of integers that is already sorted in ascending order, find
 * two numbers such that they add up to a specific target number.
 * 
 * The function twoSum should return indices of the two numbers such that they
 * add up to the target, where index1 must be less than index2. Please note that
 * your returned answers (both index1 and index2) are not zero-based.
 * 
 * You may assume that each input would have exactly one solution.
 * 
 * Input: numbers={2, 7, 11, 15}, target=9 
 * Output: index1=1, index2=2
 * 
 * </pre>
 * 
 * @author ke.zhen.xu
 */
public class Solution167TwoSumIIInputArrayIsSorted {

	public int[] twoSum(int[] numbers, int target) {
		int i = 1;
		int j = numbers.length;
		int sum = 0;
		while (i < j) {
			if ((sum = numbers[i - 1] + numbers[j - 1]) == target)
				return new int[] { i, j };
			else if (sum < target)
				i++;
			else
				j--;
		}
		return null;
	}
}
